#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

/*
	用非递归方式实现快速排序。
*/

typedef struct node
{
	int data;
	struct node *up;
	struct node *down;
} Stack;

Stack *create(void)
{
	Stack *bottom = (Stack *)malloc(sizeof(Stack));
	bottom->up = NULL;
	bottom->down = NULL;
	return bottom;
};

void destroy(Stack *p)
{
	free(p);
}

void push(Stack **top, int data)
{
	(*top)->up = (Stack *)malloc(sizeof(Stack));
	(*top)->up->down = *top;
	*top = (*top)->up;
	(*top)->data = data;
}

int pop(Stack **top)
{
	assert((*top)->down != NULL);
	int data = (*top)->data;
	*top = (*top)->down;
	free((*top)->up);
	(*top)->up = NULL;
	return data;
}

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

int median(int array[], int left, int right)
{
	int mid = (left + right) / 2;
	if (array[left] > array[mid])
	{
		swap(&array[left], &array[mid]);
	}
	if (array[mid] > array[right])
	{
		swap(&array[mid], &array[right]);
	}
	if (array[left] > array[mid])
	{
		swap(&array[left], &array[mid]);
	}
	swap(&array[mid], &array[right - 1]);
	return array[right - 1];
}

int quicksort(int array[], int left, int right)
{
	int pivot = median(array, left, right);
	int i = left, j = right;
	while (1)
	{
		while (array[i] < pivot && i < j)
			i++;
		while (array[j] >= pivot && i < j)
			j--;
		if (i < j)
		{
			swap(&array[i], &array[j]);
		}
		else
		{
			break;
		}
	}
	swap(&array[i], &array[right - 1]);
	return i;
}

void QuickSort(int array[], int n)
{
	int left = 0, right = n - 1;
	Stack *stack = create();
	push(&stack, left);
	push(&stack, right);
	while (stack->down != NULL)
	{
		right = pop(&stack);
		left = pop(&stack);
		int mid = quicksort(array, left, right);
		if (mid - 1 > left)
		{
			push(&stack, left);
			push(&stack, mid - 1);
		}
		if (mid + 1 < right)
		{
			push(&stack, mid + 1);
			push(&stack, right);
		}
	}
	free(stack);
}

int main()
{
	int array[1000];
	int i;
	for (i = 0; i < 1000; i++)
	{
		array[i] = rand() % 10000;
	}
	QuickSort(array, 1000);
	int tag = 0;
	for (int i = 0; i < 999; i++)
	{
		if (array[i] > array[i + 1])
		{
			tag = -1;
			break;
		}
	}
	printf("tag=%d\n", tag);
	return 0;
}
